package dfs;

import java.util.LinkedList;
import java.util.List;

public class 所有可能的路径 {

    List<List<Integer>> lists = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> list = new LinkedList<>();
        list.add(0);
        dfs(graph,list,0);
        return lists;
    }
    private void dfs(int[][] graph, List<Integer> list,int index) {
        if (index==graph.length-1){
            lists.add(new LinkedList<>(list));
            return;
        }
        int[] nums = graph[index];
        for (int i = 0; i < nums.length; i++) {
             list.add(nums[i]);
             dfs(graph,list,nums[i]);
             list.remove(list.size()-1);
        }
    }
}
